package leetCode.offer42;


import java.util.*;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * 要求时间复杂度为O(n)。
 * 示例1:
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释:连续子数组[4,-1,2,1] 的和最大，为6
 *
 */
public class Solution1 implements Solution{


    /**
     * 此解法会超时！！ 需优化
     * @param nums
     * @return
     */
    @Override
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        if(nums.length==2){
            int sun = nums[0]+nums[1];
            if(sun>nums[0]&&sun>nums[1]){
                return sun;
            }
            return Math.max(nums[0], nums[1]);
        }
        // 存储顺序子数组和
        int[] sum = new int[nums.length+1];
        sum[0] = 0;
        int num = 0;
        for(int i=0;i<nums.length;i++){
            num+=nums[i];
            sum[i+1] = num;
        }
        return maxProfit(sum);
    }

    public int maxProfit(int[] prices) {
        int result = -Integer.MAX_VALUE;
        int length = prices.length;
        for(int i=0;i<prices.length-1;i++) {
            int[] subPrices = new int[length];
            System.arraycopy(prices,i,subPrices,0,length);
            length--;
            int subMax = maxProfitSub(subPrices);
            if(subMax>result){
                result = subMax;
            }
        }
        return result;
    }

    public int maxProfitSub(int[] prices) {
        int result = -Integer.MAX_VALUE;
        int small = Integer.MAX_VALUE;
        int big = -Integer.MAX_VALUE;
        int smallIndex = 0;
        int bigIndex = 1;
        for(int i=0;i<prices.length-1;i++){
            if(prices[i]<small&&i<bigIndex){
                small = prices[i];
                smallIndex = i;
            }
            if(prices[i+1]>big&&i+1>=smallIndex){
                big = prices[i+1];
                bigIndex = i+1;
            }
            if(result<big-small)
                result = big - small;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] param = {1,4,1,4,3,1};
        System.out.println(new Solution1().maxProfit(param));
    }



}
